package problem236_Lowest_Common_Ancestor_of_a_Binary_Tree;

import problem105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.MySolution.TreeNode;

public class Solution {
	 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	        if(root==null||root==p||root==q)
	        	return root;
	        TreeNode left=lowestCommonAncestor(root.left,p,q);
	        TreeNode right=lowestCommonAncestor(root.right,p,q);
	        if(left!=null&&right!=null)
	        	return root;
	        return left==null?right:left;
	 }
}
